package com.lee.algorithm.recursion;

/***
 * @description: 0 1 背包
 *      给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值
 *      给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量
 *      返回袋子能装下最多的价值是多少
 *
 *      从左往右尝试，每个物品就两种选择：要 或 不要
 * @author : 青石路
 * @date: 2022/1/1 19:42
 */
public class Knapsack {

    /**
     * i以及之后的货位自由选择，形成的最大价值返回
     * @param weights 物品的重量数组
     * @param values 物品的价值数组
     * @param i 位置
     * @param alreadyWeight i位置前，已抉择好的重量
     * @param bag 袋子的容量
     * @return
     */
    public static int choice(int[] weights, int[] values, int i , int alreadyWeight, int bag) {
        if (alreadyWeight > bag) {
            return 0;
        }
        if (i == weights.length) {
            return 0;
        }
        // i 位置上的物品要 与 不要，从两种情况中取价值大的那种结果
        return Math.max(
                // 不要 i 位置上的物品
                choice(weights, values, i + 1, alreadyWeight, bag),

                // 要 i 位置上的物品
                values[i] + choice(weights, values, i+1, alreadyWeight + weights[i], bag)
        );
    }

    public static int choice2(int[] weights, int[] values, int bag) {
        int[][] dp = new int[weights.length + 1][bag + 1];
        for (int i=weights.length-1; i>=0; i--) {
            for (int j = bag; j>=0; j--) {
                dp[i][j] = dp[i+1][j];
                if (j + weights[i] <= bag) {
                    dp[i][j] = Math.max(dp[i][j], values[i] + dp[i+1][j+weights[i]]);
                }
            }
        }
        return dp[weights.length+1][bag + 1];
    }
}
